﻿using System;
using System.Collections.Generic;
using IEnumerable = System.Collections.IEnumerable;
using IEnumerator = System.Collections.IEnumerator;

namespace Klinkby.T4
{
    // This class is Eric Lippert's implementation of a immutable Stack and Queue. 
    // ** Just here for demonstration purposes **
    // http://blogs.msdn.com/ericlippert/archive/2007/12/10/immutability-in-c-part-four-an-immutable-queue.aspx

    public interface IStack<T> : IEnumerable<T>
    {
        IStack<T> Push(T value);
        IStack<T> Pop();
        T Peek();
        bool IsEmpty { get; }
    }

    public interface IQueue<T> : IEnumerable<T>
    {
        bool IsEmpty { get; }
        T Peek();
        IQueue<T> Enqueue(T value);
        IQueue<T> Dequeue();
    }

    public sealed class Stack<T> : IStack<T>
    {
        private sealed class EmptyStack : IStack<T>
        {
            public bool IsEmpty { get { return true; } }
            public T Peek() { throw new Exception("Empty stack"); }
            public IStack<T> Push(T value) { return new Stack<T>(value, this); }
            public IStack<T> Pop() { throw new Exception("Empty stack"); }
            public IEnumerator<T> GetEnumerator() { yield break; }
            IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
        }
        private static readonly EmptyStack empty = new EmptyStack();
        public static IStack<T> Empty { get { return empty; } }
        private readonly T head;
        private readonly IStack<T> tail;
        private Stack(T head, IStack<T> tail)
        {
            this.head = head;
            this.tail = tail;
        }
        public bool IsEmpty { get { return false; } }
        public T Peek() { return head; }
        public IStack<T> Pop() { return tail; }
        public IStack<T> Push(T value) { return new Stack<T>(value, this); }
        public IEnumerator<T> GetEnumerator()
        {
            for (IStack<T> stack = this; !stack.IsEmpty; stack = stack.Pop())
                yield return stack.Peek();
        }
        IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
    }

    public sealed class Queue<T> : IQueue<T>
    {
        private sealed class EmptyQueue : IQueue<T>
        {
            public bool IsEmpty { get { return true; } }
            public T Peek() { throw new Exception("empty queue"); }
            public IQueue<T> Enqueue(T value)
            {
                return new Queue<T>(Stack<T>.Empty.Push(value), Stack<T>.Empty);
            }
            public IQueue<T> Dequeue() { throw new Exception("empty queue"); }
            public IEnumerator<T> GetEnumerator() { yield break; }
            IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
        }
        private static readonly IQueue<T> empty = new EmptyQueue();
        public static IQueue<T> Empty { get { return empty; } }
        public bool IsEmpty { get { return false; } }
        private readonly IStack<T> backwards;
        private readonly IStack<T> forwards;
        private Queue(IStack<T> f, IStack<T> b)
        {
            forwards = f;
            backwards = b;
        }
        public T Peek() { return forwards.Peek(); }
        public IQueue<T> Enqueue(T value)
        {
            return new Queue<T>(forwards, backwards.Push(value));
        }
        public IQueue<T> Dequeue()
        {
            IStack<T> f = forwards.Pop();
            if (!f.IsEmpty)
                return new Queue<T>(f, backwards);
            else if (backwards.IsEmpty)
                return Queue<T>.Empty;
            else
                return new Queue<T>(Reverse(backwards), Stack<T>.Empty);
        }
        public IEnumerator<T> GetEnumerator()
        {
            foreach (T t in forwards) yield return t;
            foreach (T t in Reverse(backwards)) yield return t;
        }
        IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
        static IStack<T> Reverse(IStack<T> stack)
        {
            IStack<T> r = Stack<T>.Empty;
            for (IStack<T> f = stack; !f.IsEmpty; f = f.Pop())
                r = r.Push(f.Peek());
            return r;
        }
    }
}
